package chain;

/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class Solution_4 {

	/**
	 * 递归实现
	 */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

		if (l1 == null) {
			return l2;
		}

		if (l2 == null) {
			return l1;
		}

		if (l1.val < l2.val) {
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		} else {
			l2.next = mergeTwoLists(l1, l2.next);
			return l2;
		}

	}

	/**
	 * 简单迭代实现
	 */
	public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

		// 定义头结点，方便建立新链表
		ListNode dummy = new ListNode(-1);
		// 用来遍历链表的指针
		ListNode l3 = dummy;

		// 同时遍历两个链表并拼接值较小的结点到新链表中，同步更新链表指针，直至某个链表遍历结束
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				l3.next = l1;
				l1 = l1.next; // 移动l1的指针
			} else {
				l3.next = l2;
				l2 = l2.next; // 移动l2的指针
			}
			l3 = l3.next; // 移动l3的指针
		}

		// 将未遍历完的链表直接拼接至新链表(因为两个链表本身就是有序的)
		if (l1 != null) {
			l3.next = l1;
		}
		if (l2 != null) {
			l3.next = l2;
		}

		// 丢掉第一个无意义的头结点，直接返回第二个节点
		return dummy.next;

	}

	public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val; this.next = next;
		}
	}
}